• Arthur Samuel (1959): Field of study of that gives computers the ability to learn without being explicitly programmed.
• Tom Mitchel (1998): A Well-posed Learning Problem is *A computer program is said to learn from experience E with repsect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

We mainly talks about two types of algorithm:

• Supervised Learning
• Unsupervised Learning
• Others: Reinforcement Learning, Recommender System.

And Practical advice for applying learning algorithm

Notations:

1. \(m\) is Number of training examples.
2. \(x\)'s is "input" variable / feature.
3. \(y\)'s is "output" variable / "target" variables.
4. \((x,y)\) is one training example.
5. \((x^{(i)},y^{(i)})\) is the \(i\)th example, \(i\) starts from \(0\).
6. \(h\) is called hypothesis, it maps the input to output. In this lecture, we represent \(h\) using linear function, thus it's called linear regression. For linear regression with one variable, it's called univariate linear regression. For example, the univariate linear regression is usually written as: \(h_\theta (x) = \theta_0 + \theta_1 x\). The \(\theta\) here represents the coefficient variables. Sometimes it's written as \(h(x)\) as a shorthand.

Since the hypothesis is written as \(h_\theta (x) = \theta_0 + \theta_1 x\), where \(\theta_i\)'s are the parameters, then how to choose \(\theta_i\)'s? The idea is to choose \(\theta_0, \theta_1\) so that \(h_\theta (x)\) is close to \(y\) for our training examples \((x,y)\). More formally, we want to \[ \underset{\theta_0,\theta_1}{\text{minimize}} \frac{1}{2m}\sum_{i=1}^{m}\left( h_\theta(x^{(i)}) - y^{(i)} \right)^2 \], where \(m\) is the number of trainnig examples. To recap, we're minimizing half of the averaging error. Note that the variable here are \(\theta\)s, and \(x\) and \(y\)'s are constants.

By convention, we define the cost function \(J(\theta_0,\theta_1)\) to represent the objective function. That is

This cost function is also called squared error function. There are other cost functions, but it turns out that squared error function is a resonable choice and will work for most of regression problem.

Before getting a intuition about the cost function, let's have a recap, we now have

1. Hypothesis: \[h_\theta (x) = \theta_0 + \theta_1 x\]
2. Parameters: \[\theta_0,\theta_1\]
3. Cost Function: \[J(\theta_0,\theta_1) = \frac{1}{2m}\sum_{i=1}^{m}\left( h_\theta(x^{(i)}) - y^{(i)} \right)^2 \]
4. Goal: \[\underset{\theta_0,\theta_1}{\text{minimize}} J(\theta_0,\theta_1)\]

In order to visualize our cost function, we use a simplified hypothesis function: \(h_\theta (x) = \theta_1 x\), which sets \(\theta_0\) to \(0\). So now we have

1. Hypothesis: \[h_\theta (x) = \theta_1 x\]
2. Parameters: \[\theta_1\]
3. Cost Function: \[J(\theta_1) = \frac{1}{2m}\sum_{i=1}^{m}\left( h_\theta(x^{(i)}) - y^{(i)} \right)^2 \]
4. Goal: \[\underset{\theta_1}{\text{minimize}} J(\theta_1)\]

So now let's compare function \(h_\theta (x)\) and function \(J(\theta_1)\):

Then let's come back to the original function, where we don't have the constrain that \(\theta_0 = 0\). The comparison is like

Now we have some function \(J(\theta_0,\theta_1)\) and we want to \(\underset{\theta_0,\theta_1}{\text{minimize}}J(\theta_0,\theta_1)\), we use gradient descent here, which

1. Start with some \(\theta_0,\theta_1\),
2. Keep changing \(\theta_0,\theta_1\) to reduce \(J(\theta_0,\theta_1)\), until we hopefully end up at a minimum.

To help understand gradient descent, suppose you are standing at one point on the hill, and you want to take a small step to step downhill as quickly as possible, then you would choose the deepest direction to downhill. You keep doing this until to get to a local minimum.

But if you start with a different initial position, gradient descent will take you to a (very) different position.

Notation:

1. number of features: \(n\)
2. input (features) of \(i^{\text{th}}\) training example: \(x^{(i)}\)
3. value of feature \(j\) in \(i^{th}\) training example. \(x^{(i)}_{j}\)

Now our hypothesis is \(h_\theta (x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \dots + \theta_n x_n \). For convenience of notation, define \(x_0 = 1\), or \(x^{(i)}_0 = 1\). So now we define our hypothesis as

where \(\theta\) is a \(n+1\) dimension vector.

So now our new algorithm becomes Note that our new algorithm for \(\theta_0\) is just like the old one since \(x_0^{(i)} \) is 1.

Idea: Make sure features are on a similar scale, then gradient descent will converge more quickly.

Take a 2D example, if the dimension of \(x_1\) is much larger than the dimension of \(x_2\), then the search region is a long ellipsis shape which is make gradient much difficult to find the minimum. We can rescale all features to [0,1] so the contours now become a circle.

Usually we get every feature into approximately a \(-1 \leq x \leq 1\) range. But it need not to be exactly. Say \(-3 \leq x \leq 3 \) is OK.

Mean normalization: Replace \(x_i\) with \(x_i - \mu_i\) to make features have approximately zero mean. Note that this does not apply to \(x_0 = 1\).

To make sure gradient descent is working correctly, draw the figure the value of \(J(\theta)\) versus the number of iterations.

For sufficiently small \(\alpha\), \(J(\theta\) should decrease on every iteration. But if \(\alpha\) is too small, gradient descent can converge too slow. To choose \(\alpha\) try \( \dots, 0.001, 0.003,0.01, 0.03,0.1, 0.3,1, \dots\), roughly a 3x larger.

You need to choose a good feature instead of just using what you're provided. For example, for housing price prediction, you are provided with the frontage and depth feature, you can define a feature called area = frontage x depth.

Or sometimes use a polynomial function would be better. If the feature is not enough, you could use size, size^2, size^3 as features.

Or you can use square root as feature. How to find the minimum of \(J(\theta)\) analytically?

By Calculus, we can take the partial derivatives of each variable, and set it to 0.

Normal Equation: Then we can compute \(\theta = (X^T X)^{-1} X^T y\) The Octave code is:

pinv(X' * X) * X' * y

Compare Gradient Descent with Normal Equation.

Use pinv in Octave should not be a problem. What if \(X^T X\) is non-invertible?

1. Reduent features (linearyly dependant). E.g. \(x_1\) = size in feet, \(x_2\) size in m^2.
2. Too many features (e.g. $m ≤ n). Delete some features, or use regulariation.

\(h_\theta(x) = \sum_{j=0}^{n} \theta_j x_j = \theta^T x\)

%unvectorized implemenetation
  predictaion = 0.0;
  for j = 1;n+1,
      prediction = prediction + theta(j) * x(j)
  end;
  %vectorized implementation
  prediction = thteta' * x;

Applying linear regression to a classification problem is not a good idea.

You can use 0.5 as a threshhold to do the prediction based on the h_θ(x) value. However, this is not a good idea since when adding a new sample point, the hypothesis will change. Besides, the return value for h_θ(x) could be not in the range [0, 1], thus making the prediction rather confusing. Logistic Regression, though the word regression, is used to do the classification job and the hypothesis can be guaranteed in the range [0,1].

It's a line that separates the regions where the hypothesis predicts 1 or 0.

Since \(g(z) \geq 0.5\) when \(z \geq 0.5\), which means that \(h_\theta(x) \geq 0.5\) whenever \(\theta^{T} x \geq 0\)

How to fit the parameters θ for Logistic Regression? We define the cost function as below since \(h_\theta(x)\) is in the range [0,1].

Remember that the Logistic regression cost function is in two parts, since y can be 0 or 1 only, we can write the cost function in a new way:

Remember that gradient descent is like:

where the partial derivatives is like:

Note that the Octave start from 1 instead of 0.

One-vs-all is also called one-vs-rest.

The method is:

For Logistic regression:

How to solve the problem?

The idea behind regulation is that: Note that we didn't penalize θ_0

What if λ is too large?

When using normal equation:

Now update θ_0 separately

Use quadratic features will results in a lot of features.

There is one learning algorithm of the brain

Neuron model: Logistic unit

Neural Network is a group of this neural.

Forward propagation: Vectorized implementation

Bias unit:

The last layer is like Logistic Regression, but Neural Network learning its own features.

OR Function

NOT Function

The input layer has only x_1 and x_2. The second layer compute the feature (x_1 AND x_2), and the feature (NOT x_1) AND (NOT x_2). The third layer use the feature computed in layer 2 and do an OR operation to simulates a XNOR operation.

Handwritten digit classification

Use an extension of the One-vs-all method.

This is the cost function

Forward Propagation, computing all the activations:

Backpropagation algorithm, computing the gradient:

The name "back" comes from the order we compute the "error" Backpropagation algorithm

In Neural Network our parameters are matrices, and we need to unroll it into vectors.

Use nummerical estimation of gradients to check.

We need to provide an initial value for gradient fescent and advanced optimization method.

Zero Initialization will result in identical values.

To solve this problem, we use random initialization to break the symmerty.

How to train a neural network

1. Get more training examples
2. Try smaller sets of features
3. Try getting additional features.
4. Try adding polynomial features
5. Try decreasing λ.
6. Try increasing λ.

Hypothesis can be overfitting.

We can evaluate our hypothesis by separate our date into training set and test set.

To address this problem, we divide our data set into three parts: training set, cross validation set, and test set.

Use cross validation error to selection the model degree and use test set error to select θ.

Bias (undearfit) Variance (overfit)